package com.study;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-12 14:36
 * @version: 1.0
 * @description: 两数之和
 *    给定一个数组，从数组中找出两个数，满足相加之和等于target，不可重复使用下标，以数组形式返回两数下标
 *
 *    考点：标记法
 *
 * 升级版本：给你一个升序排列的数组，
 *  两个解法：二分查找和双指针
 **/
public class NumSum {
    public static void main(String[] args) {

        System.out.println(Arrays.toString(solution(new int[] {1,-1,10,3,2,6,5,8},14)));
        System.out.println(Arrays.toString(twoSearch(new int[] {-1,1,2,3,5,6,8,10},14)));
        System.out.println(Arrays.toString(twoPoint(new int[] {-1,1,2,3,5,6,8,10},14)));

    }

    /**
     * 双指针解法
     * @param numbers
     * @param target
     * @return
     */
    private static int[] twoPoint(int[] numbers, int target) {

        for (int left = 0,right = numbers.length -1 ; left <= right ; ) {
            if (numbers[left] + numbers[right] == target){
                return new int[] {left,right};
            }else if (numbers[left] + numbers[right] > target){
                right--;
            }else if(numbers[left] + numbers[right] < target){
                left++;
            }
        }
        return new int[0];
    }

    private static int[] twoPoint1(int[] numbers, int target) {
        for (int l = 0,r = numbers.length -1; l <= r ; ) {
            if (numbers[l] + numbers[r] == target){
                return new int[]{l,r};
            }else if (numbers[l] + numbers[r] > target){
                r--;
            }else {
                l++;
            }
        }
        return new int[0];
    }

    /**
     * 有序数组求两个数的和，二分查找
     * @param nums
     * @param target
     * @return
     */
    private static int[] twoSearch(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {
            int low = 0,high = nums.length - 1;
            while (low <= high){
                int mid = low + (high - low)/2;
                if (target - nums[i] == nums[mid]){
                    return new int[]{i,mid};
                }else if(target - nums[i] > nums[mid]){
                    low = mid + 1;
                }else if(target - nums[i] < nums[mid]){
                    high = mid - 1;
                }
            }
        }
        return new int[0];
    }

    /**
     * 标记法 解无序数组
     * 需要一个额外的 map 存储已经查询过的值
     * @param nums
     * @param target
     * @return
     */
    private static int[] solution(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])){
                return new int[] {map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }

    private static int[] solution1(int[] nums, int target){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])){
                return new int[]{i,map.get(target - nums[i])};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }
}
